import java.util.*;

class Solution6 {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> result = new ArrayList<Integer>();

        List<Integer>[] adj = new List[n];
        for(int i = 0; i < n; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        for(int[] i : edges) {
            adj[i[0]].add(i[1]);
            adj[i[1]].add(i[0]);
        }

        int[] parent = new int[n];
        Arrays.fill(parent, -1);

        int x = findLongestNode(0, parent, adj);
        int y = findLongestNode(x, parent, adj);

        List<Integer> tmp = new ArrayList<Integer>();
        parent[x] = -1;
        while(y != -1) {
            tmp.add(y);
            y = parent[y];
        }
        if(tmp.size() % 2 == 0) {
            result.add(tmp.get(tmp.size() / 2 - 1));
            result.add(tmp.get(tmp.size() / 2));
        }else {
            result.add(tmp.get(tmp.size() / 2));
        }
        return result;
    }

    public Integer findLongestNode(int u, int[] parent, List<Integer>[] adj) {
        int n = adj.length;
        Queue<Integer> queue = new ArrayDeque<Integer>();
        boolean[] visit = new boolean[n];
        visit[u] = true;
        queue.offer(u);
        int node = -1;
        while(!queue.isEmpty()) {
            int curr = queue.poll();
            node = curr;
            for(int v : adj[curr]) {
                if(!visit[v]) {
                    visit[v] = true;
                    parent[v] = curr;
                    queue.offer(v);
                }
            }
        }
        return node;
    }
}